Atrist

# 题目: 229. 求众数 II

给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。

# 示例1:

输入：[3,2,3]
输出：[3]

# 示例2:

输入：nums = [1]
输出：[1]

# 提示：

# 题解1： 哈希统计出现次数

我们可以借助哈希表，将数字作为键名，出现的次数作为键值。一次遍历之后，再从哈希表中进行遍历找出出现次数大于[n/3]的元素。

# 代码

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var majorityElement = function(nums) {
    let map = new Map()
    let res = []
    let n = Math.floor(nums.length/3)
    for(let i of nums){
        map.set(i, (map.get(i) || 0) + 1)
    }
    for(let [key,value] of map){
        if(value>n) res.push(key)
    }
    return res
};

# 题解2： 摩尔投票法

# 摩尔投票法

摩尔投票法：摩尔投票法的核心思想为对拼消耗。首先我们考虑最基本的摩尔投票问题，比如找出一组数字序列中出现次数大于总数 的数字（并且假设这个数字一定存在）。我们可以直接利用反证法证明这样的数字只可能有一个。

摩尔投票算法的核心思想是基于这个事实： 每次从序列里选择两个不相同的数字删除掉（或称为「抵消」），最后剩下一个数字或几个相同的数字，就是出现次数大于总数一半的那个元素。假设我们当前数组中存在次数大于总数一半的元素为 x，数组的总长度为 n，则我们可以把数组分为两部分，一部分为相同的 k 个元素 x，另一部分为 对个不同的元素配对，此时我们假设还存在另外一个次数大于总数一半的元素 y，则此时 y 因该满足 ，但是按照我们之前的推理 y 应当满足 ，二者自相矛盾。

# 算法

借助摩尔投票法，因为我需要找到[n/3]的元素个数，所以我们每次从序列里选择三个不同的数字删掉。

  • 我们每次检测当前元素是否为第一个选中的元素或者第二个选中的元素。
  • 每次我们发现当前元素与已经选中的两个元素都不相同，则进行抵消一次。
  • 如果存在最终选票大于 0 的元素，我们还需要再次统计已选中元素的次数,检查元素的次数是否大于 。

# 代码

# 参考资料

← 230. 二叉搜索树中第K小的元素 →